//
// kmp 字符串匹配
// 难度：困难
//

#define MAX_NEXT_SIZE 10000

#include "GString.h"

// 获取 next 数组
int *getNext(const GString &subStr) {
    int *next = new int[MAX_NEXT_SIZE];
    int subMatcher = -1, mainMatcher = 0;
    // 第一个位置标记为 -1
    next[mainMatcher] = subMatcher;
    // _data 的最后一个字符不用计算
    while (mainMatcher < subStr.length() - 1) {
        // 遇到标记或者匹配成功，前进后将后指针赋值为前指针
        // 也就是说，后指针指向的位置的前缀串和前指针的前缀串相同
        if (subMatcher == -1 || subStr[subMatcher] == subStr[mainMatcher]) {
            subMatcher++;
            mainMatcher++;
            next[mainMatcher] = subMatcher;
        } // 否则，前指针回退，寻找匹配的串
        else {
            subMatcher = next[subMatcher];
        }
    }
    return next;
}

[[maybe_unused]] bool kmpMatch(const GString &mainStr, const GString &subStr) {
    // 计算 next 数组
    int *next = getNext(subStr);
    int mainIndex = 0, subIndex = 0;
    while (mainIndex < mainStr.length() && subIndex < subStr.length()) {
        // 到达标记位置或者匹配成功，前进
        if (subIndex == -1 || mainStr[mainIndex] == subStr[subIndex]) {
            mainIndex++;
            subIndex++;
        } // 否则，前指针回退，寻找匹配的串
        else {
            subIndex = next[subIndex];
        }
    }
    // 字串遍历完即匹配成功
    if (subIndex == subStr.length()) {
        return true;
    }
    return false;
}

